Identifying hubs in directed networks.

Nodes in networks that exhibit high connectivity, also called "hubs," play a critical role in determining the structural and functional properties of networked systems. However, there is no clear definition of what constitutes a hub node in a network, and the classification of network hubs in existing work has either been purely qualitative or relies on ad hoc criteria for thresholding continuous data that do not generalize well to networks with certain degree sequences. Here we develop a set of efficient nonparametric methods that classify hub nodes in directed networks using the Minimum Description Length principle, effectively providing a clear and principled definition for network hubs. We adapt our methods to both unweighted and weighted networks, and we demonstrate them in a range of example applications using real and synthetic network data.

Heterogeneous message passing for heterogeneous networks.

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

Characterizing network circuity among heterogeneous urban amenities.

The spatial configuration of urban amenities and the streets connecting them collectively provide the structural backbone of a city, influencing its accessibility, vitality and ultimately the well-being of its residents. Most accessibility measures focus on the proximity of amenities in space or along transportation networks, resulting in metrics largely determined by urban density alone. These measures are unable to gauge how efficiently street networks can navigate between amenities, since they neglect the circuity component of accessibility. Existing measures also often require ad hoc modelling choices, making them less flexible for different applications and difficult to apply in cross-sectional analyses. Here, we develop a simple, principled and flexible measure to characterize the circuity of accessibility among heterogeneous amenities in a city, which we call the pairwise circuity (PC). The PC quantifies the excess travel distance incurred when using the street network to route between a pair of amenity types, summarizing both spatial and topological correlations among amenities. Measures developed using our framework exhibit significant statistical associations with a variety of urban prosperity and accessibility indicators when compared with an appropriate null model, and we find a clear separation in the PC values of cities according to development level and geographical region.

Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection.

The task of community detection, which aims to partition a network into clusters of nodes to summarize its large-scale structure, has spawned the development of many competing algorithms with varying objectives. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model, while other methods are descriptive, dividing a network according to an objective motivated by a particular application, making it challenging to compare these methods on the same scale. Here we present a solution to this problem that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model. This allows us to compute the description length of a network and its partition under arbitrary objectives, providing a principled measure to compare the performance of different algorithms without the need for "ground-truth" labels. Our approach also gives access to instances of the community detection problem that are optimal to any given algorithm and in this way reveals intrinsic biases in popular descriptive methods, explaining their tendency to overfit. Using our framework, we compare a number of community detection methods on artificial networks and on a corpus of over 500 structurally diverse empirical networks. We find that more expressive community detection methods exhibit consistently superior compression performance on structured data instances, without having degraded performance on a minority of situations where more specialized algorithms perform optimally. Our results undermine the implications of the "no free lunch" theorem for community detection, both conceptually and in practice, since it is confined to unstructured data instances, unlike relevant community detection problems which are structured by requirement.

Impact of urban structure on infectious disease spreading.

The ongoing SARS-CoV-2 pandemic has been holding the world hostage for several years now. Mobility is key to viral spreading and its restriction is the main non-pharmaceutical interventions to fight the virus expansion. Previous works have shown a connection between the structural organization of cities and the movement patterns of their residents. This puts urban centers in the focus of epidemic surveillance and interventions. Here we show that the organization of urban flows has a tremendous impact on disease spreading and on the amenability of different mitigation strategies. By studying anonymous and aggregated intra-urban flows in a variety of cities in the United States and other countries, and a combination of empirical analysis and analytical methods, we demonstrate that the response of cities to epidemic spreading can be roughly classified in two major types according to the overall organization of those flows. Hierarchical cities, where flows are concentrated primarily between mobility hotspots, are particularly vulnerable to the rapid spread of epidemics. Nevertheless, mobility restrictions in such types of cities are very effective in mitigating the spread of a virus. Conversely, in sprawled cities which present many centers of activity, the spread of an epidemic is much slower, but the response to mobility restrictions is much weaker and less effective. Investing resources on early monitoring and prompt ad-hoc interventions in more vulnerable cities may prove helpful in containing and reducing the impact of future pandemics.

Clustering of heterogeneous populations of networks.

Statistical methods for reconstructing networks from repeated measurements typically assume that all measurements are generated from the same underlying network structure. This need not be the case, however. People's social networks might be different on weekdays and weekends, for instance. Brain networks may differ between healthy patients and those with dementia or other conditions. Here we describe a Bayesian analysis framework for such data that allows for the fact that network measurements may be reflective of multiple possible structures. We define a finite mixture model of the measurement process and derive a Gibbs sampling procedure that samples exactly from the full posterior distribution of model parameters. The end result is a clustering of the measured networks into groups with similar structure. We demonstrate the method on both real and synthetic network populations.

Connecting intercity mobility with urban welfare.

While significant effort has been devoted to understand the role of intraurban characteristics on sustainability and growth, much remains to be understood about the effect of interurban interactions and the role cities have in determining each other's urban welfare. Here we consider a global mobility network of population flows between cities as a proxy for the communication between these regions, and analyze how it correlates with socioeconomic indicators. We use several measures of centrality to rank cities according to their importance in the mobility network, finding PageRank to be the most effective measure for reflecting these prosperity indicators. Our analysis reveals that the characterization of the welfare of cities based on mobility information hinges on their corresponding development stage. Namely, while network-based predictions of welfare correlate well with economic indicators in mature cities, for developing urban areas additional information about the prosperity of their mobility neighborhood is needed. We develop a simple generative model for the allocation of population flows out of a city that balances the costs and benefits of interaction with other cities that are successful, finding that it provides a strong fit to the flows observed in the global mobility network and highlights the differences in flow patterns between developed and developing urban regions. Our results hint towards the importance of leveraging interurban connections in service of urban development and welfare.

Integrating online and offline data for crisis management: Online geolocalized emotion, policy response, and local mobility during the COVID crisis.

Integrating online and offline data is critical for uncovering the interdependence between policy and public emotional and behavioral responses in order to aid the development of effective spatially targeted interventions during crises. As the COVID-19 pandemic began to sweep across the US it elicited a wide spectrum of responses, both online and offline, across the population. Here, we analyze around 13 million geotagged tweets in 49 cities across the US from the first few months of the pandemic to assess regional dependence in online sentiments with respect to a few major COVID-19 related topics, and how these sentiments correlate with policy development and human mobility. In this study, we observe universal trends in overall and topic-based sentiments across cities over the time period studied. We also find that this online geolocalized emotion is significantly impacted by key COVID-19 policy events. However, there is significant variation in the emotional responses to these policies across the cities studied. Online emotional responses are also found to be a good indicator for predicting offline local mobility, while the correlations between these emotional responses and local cases and deaths are relatively weak. Our findings point to a feedback loop between policy development, public emotional responses, and local mobility, as well as provide new insights for integrating online and offline data for crisis management.

Belief propagation for networks with loops.

Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortcoming that it works poorly in the common case of networks that contain short loops. Here, we provide a solution to this long-standing problem, deriving a belief propagation method that allows for fast calculation of probability distributions in systems with short loops, potentially with high density, as well as giving expressions for the entropy and partition function, which are notoriously difficult quantities to compute. Using the Ising model as an example, we show that our approach gives excellent results on both real and synthetic networks, improving substantially on standard message passing methods. We also discuss potential applications of our method to a variety of other problems.

Publisher Correction: Robust design from systems physics.

An amendment to this paper has been published and can be accessed via a link at the top of the paper.

Robust design from systems physics.

A crucial challenge in engineering modern, integrated systems is to produce robust designs. However, quantifying the robustness of a design is less straightforward than quantifying the robustness of products. For products, in particular engineering materials, intuitive, plain language terms of strong versus weak and brittle versus ductile take on precise, quantitative meaning in terms of stress-strain relationships. Here, we show that a "systems physics" framing of integrated system design produces stress-strain relationships in design space. From these stress-strain relationships, we find that both the mathematical and intuitive notions of strong versus weak and brittle versus directly characterize the robustness of designs. We use this to show that the relative robustness of designs against changes in problem objectives has a simple graphical representation. This graphical representation, and its underlying stress-strain foundation, provide new metrics that can be applied to classes of designs to assess robustness from feature- to system-level.

Mixing Patterns in Interdisciplinary Co-Authorship Networks at Multiple Scales.

There are inherent challenges to interdisciplinary research collaboration, such as bridging cognitive gaps and balancing transaction costs with collaborative benefits. This raises the question: Does interdisciplinary research collaboration necessarily result in disciplinary diversity among collaborators? We aim to explore this question by assessing collaborative preferences in interdisciplinary research at multiple scales through the examinination of disciplinary mixing patterns at the individual, dyadic, and team level in a coauthor network from the field of artificial intelligence in education, an emerging interdisciplinary area. Our key finding is that disciplinary diversity is reflected by diverse research experiences of individual researchers rather than diversity within pairs or groups of researchers. We also examine intergroup mixing by applying a novel approach to classify the active and non-active researchers in the collaboration network based on participation in multiple teams. We find a significant difference in indicators of academic performance and experience between the clusters of active and non-active researchers, suggesting intergroup mixing as a key factor in academic success. Our results shed light on the nature of team formation in interdisciplinary research, as well as highlight the importance of interdisciplinary training.

Balance in signed networks.

We consider signed networks in which connections or edges can be either positive (friendship, trust, alliance) or negative (dislike, distrust, conflict). Early literature in graph theory theorized that such networks should display "structural balance," meaning that certain configurations of positive and negative edges are favored and others are disfavored. Here we propose two measures of balance in signed networks based on the established notions of weak and strong balance, and we compare their performance on a range of tasks with each other and with previously proposed measures. In particular, we ask whether real-world signed networks are significantly balanced by these measures compared to an appropriate null model, finding that indeed they are, by all the measures studied. We also test our ability to predict unknown signs in otherwise known networks by maximizing balance. In a series of cross-validation tests we find that our measures are able to predict signs substantially better than chance.

From the betweenness centrality in street networks to structural invariants in random planar graphs.

The betweenness centrality, a path-based global measure of flow, is a static predictor of congestion and load on networks. Here we demonstrate that its statistical distribution is invariant for planar networks, that are used to model many infrastructural and biological systems. Empirical analysis of street networks from 97 cities worldwide, along with simulations of random planar graph models, indicates the observed invariance to be a consequence of a bimodal regime consisting of an underlying tree structure for high betweenness nodes, and a low betweenness regime corresponding to loops providing local path alternatives. Furthermore, the high betweenness nodes display a non-trivial spatial clustering with increasing spatial correlation as a function of the edge-density. Our results suggest that the spatial distribution of betweenness is a more accurate discriminator than its statistics for comparing  static congestion patterns and  its evolution across cities as demonstrated by analyzing 200 years of street data for Paris.